﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Runtime.Serialization;

//https://www.cnblogs.com/zouqiang/p/13094018.html
//https://blog.csdn.net/qq_41044598/article/details/126067510?spm=1001.2014.3001.5501
//时间=hash映射的时间O(1)+链表遍历的时间
namespace Project2.容器
{
    internal class MyDictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
    {
        private struct Entry//链表的结构
        {
            public int hashCode;

            public int next;

            public TKey key;

            public TValue value;
        }

        /// <summary>
        /// Hash桶
        /// </summary>
        private int[] buckets;//存的元素是entries的index，而不是HashCode，是当前筒管理的链表的头节点的index

        /// <summary>
        /// 所有键值对条目数组
        /// </summary>
        private Entry[] entries;

        /// <summary>
        /// 当前entries内的元素数量，也就是所有的字典元素，不是entries数组的容量
        /// </summary>
        private int entryCount;

        /// <summary>
        /// 对比函数
        /// </summary>
        private IEqualityComparer<TKey> comparer;

        /// <summary>
        /// 当前版本，防止迭代过程中集合被更改
        /// </summary>
        private int version;

        /// <summary>
        /// entries被删除释放出来的位置的索引
        /// </summary>
        private int freeListIndex;

        //freeList是一个空闲链表，用来管理被清理出来的元素，优先使用

        /// <summary>
        /// entries空闲数量
        /// </summary>
        private int freeCount;

        public MyDictionary()
        {
            comparer = EqualityComparer<TKey>.Default;
        }

        //索引器
        public TValue this[TKey key]
        {
            set
            {
                Insert(key, value, false);
            }
            get
            {
                int index = FindEntry(key);//找结构体的index
                if (index >= 0)
                {
                    return entries[index].value;
                }//-1说明筒是空的，没有这个key
                throw new Exception("TKey 异常");
            }
        }

        /// <summary>
        /// 查找键值对条目
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        private int FindEntry(TKey key)
        {
            if (key == null)
            {
                throw new Exception("key 异常");
            }

            if (buckets != null)
            {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;// & 0x7FFFFFFF 即 2进制011111...，是为了确保 hashCode 是一个正整数
                int bucketId = hashCode % buckets.Length;//第几个筒（数组）
                //每个筒有一个链表（拉链法解冲突）
                int entriesHead = buckets[bucketId];//指向表头
                for (int i = entriesHead; i >= 0; i = entries[i].next)//遍历链表的元素
                {
                    //判断hashCode相等且key相等 则返回索引   如果不相等 获取next
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
                }
            }
            return -1;
        }

        /// <summary>
        /// 初始化
        /// </summary>
        /// <param name="capacity">容量</param>
        private void Initialize(int capacity)
        {
            int size = MyHashHelpers.GetPrime(capacity);//获取该容量匹配的质数（0-3）
            buckets = new int[size];//初始化桶数组
            //当 bucket 没有指向任何 entry 时,它的值为-1。（buckets全部初始化为-1）
            for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;//桶数组全部赋值为-1
            entries = new Entry[size];//初始化容量
            //链表是有大小的

            freeListIndex = -1;//指向-1
        }

        public void Add(TKey key, TValue value)
        {
            Insert(key, value, true);
        }

        /// <summary>
        /// 插入
        /// </summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        /// <param name="add"></param>
        private void Insert(TKey key, TValue value, bool add)
        {
            if (key == null)
            {
                throw new Exception("key == null 异常");
            }

            if (buckets == null) Initialize(0);//初始化筒
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;//01111111 11111111 11111111 11111111 忽略符号位
            int targetBucket = hashCode % buckets.Length;//获得hashCode在buckets中存放在位置

            int collisionCount = 0;//冲突数量

            //从hash桶中获取索引     cur = entries[cur].next 继续获取拉链下一个数据
            //有一样的key就更新value
            for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next)
            {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))//如果键值对条目数组索引位置hashCode等于key的hashCode 且key相等 赋值
                {
                    if (add)
                    {
                        throw new Exception("key已存在 异常");
                    }
                    entries[i].value = value;//更新value
                    version++;
                    return;
                }
                //如果不相等 冲突+1（哈希冲突）
                collisionCount++;
            }

            //创建一个拉链数据
            int curIndex;//记录当前元素要存放的位置
            if (freeCount > 0)//有空闲位置，优先使用清理出来的位置（之前用过的位置）
            {
                //curIndex = freeListIndex;
                //freeListIndex = entries[curIndex].next;

                int nextFreeListIndex = entries[freeListIndex].next;//先记录下一个
                curIndex = freeListIndex;
                freeListIndex = nextFreeListIndex;//更新

                freeCount--;
            }
            else
            {
                if (entryCount == entries.Length)//如果键值对条目数组已满
                {
                    Resize();//调整大小
                    targetBucket = hashCode % buckets.Length;//重现获取hashCode在buckets中存放在位置
                }
                curIndex = entryCount;//取数组空闲的位置index
                entryCount++;
            }
            // 这里的index通常是上一次释放数据的位置或者entries数组的下一个空余位置
            //头插法
            entries[curIndex].hashCode = hashCode;
            //把原hash桶中索引的键值对条目索引赋值到当前键值对条目的下一个位
            entries[curIndex].next = buckets[targetBucket];
            entries[curIndex].key = key;
            entries[curIndex].value = value;

            buckets[targetBucket] = curIndex;//更新表头
            version++;

            // 如果碰撞次数大于设置的最大碰撞次数，那么触发Hash碰撞扩容
            if (collisionCount > 100 && (comparer == null || comparer == EqualityComparer<TKey>.Default))
            {
                comparer = EqualityComparer<TKey>.Default;//使用新的对比hash函数
                Resize(entries.Length, true);
            }
        }

        /// <summary>
        /// 调整大小
        /// </summary>
        private void Resize()
        {
            Resize(MyHashHelpers.ExpandPrime(entryCount), false);
        }

        /// <summary>
        /// 调整大小
        /// </summary>
        /// <param name="newSize">一般是素数,字典的容量</param>
        /// <param name="forceNewHashCodes">强制使用新的hashcode方法</param>
        private void Resize(int newSize, bool forceNewHashCodes)
        {
            int[] newBuckets = new int[newSize];//新的hash桶
            for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;

            Entry[] newEntries = new Entry[newSize];//新的键值对条目数组

            Array.Copy(entries, 0, newEntries, 0, entryCount);//拷贝老的键值对条目数组到新的键值对条目数组

            if (forceNewHashCodes)//强制使用新的hashcode
            {
                for (int i = 0; i < entryCount; i++)
                {
                    if (newEntries[i].hashCode != -1)//过滤未使用的
                    {
                        newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);//使用新HashCode函数重新计算Hash值
                    }
                }
            }
            //筒大了，重新分配
            for (int i = 0; i < entryCount; i++)
            {
                int bucket = newEntries[i].hashCode % newSize;//获取hash桶索引
                //头插法
                newEntries[i].next = newBuckets[bucket];
                //第一次 newBuckets[bucket]==-1 第n次 newBuckets[bucket]==上次赋值索引
                newBuckets[bucket] = i;//更新头节点
            }
            buckets = newBuckets;
            entries = newEntries;
        }

        public bool Remove(TKey key)
        {
            if (key == null)
            {
                throw new Exception("异常");
            }

            if (buckets != null)
            {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                int bucket = hashCode % buckets.Length;
                int pre = -1;
                for (int cur = buckets[bucket]; cur >= 0; cur = entries[cur].next)//遍历链表找
                {
                    if (entries[cur].hashCode == hashCode && comparer.Equals(entries[cur].key, key))
                    {
                        if (pre < 0)//找到表尾了
                        {
                            buckets[bucket] = entries[cur].next;
                            //找到元素后，如果pre< 0，代表当前是bucket中第一个元素就找到了，pre还没有更新
                            //那么直接让bucket内下标赋值为 entries[cur].next即可，表头指向第二个元素
                        }
                        else
                        {
                            entries[pre].next = entries[cur].next;//代表当前元素处于bucket单链表中间位置，需要将该元素的头结点和尾节点相连起来,防止链表中断
                        }
                        entries[cur].hashCode = -1;
                        entries[cur].next = freeListIndex;//把删除的元素的下一个指向旧的freeListIndex
                        entries[cur].key = default(TKey);
                        entries[cur].value = default(TValue);
                        freeListIndex = cur;//更新freeListIndex指向，下一次Add元素会优先Add到该位置
                        freeCount++;
                        version++;
                        return true;
                    }
                    pre = cur;//记录一下前一个，然后后移
                }
            }
            return false;
        }

        public void Clear()
        {
            if (entryCount > 0)//有元素才开始清理
            {
                for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;//清理链表
                Array.Clear(entries, 0, entryCount);//清理数组
                freeListIndex = -1;
                entryCount = 0;
                freeCount = 0;
                version++;
            }
        }

        public bool ContainsKey(TKey key)
        {
            return FindEntry(key) >= 0;
        }

        public bool ContainsValue(TValue value)
        {
            if (value == null)//存的就是空值
            {
                for (int i = 0; i < entryCount; i++)
                {
                    if (entries[i].hashCode >= 0 && entries[i].value == null)//确保有key
                    {
                        return true;
                    }
                }
            }
            else
            {
                EqualityComparer<TValue> @default = EqualityComparer<TValue>.Default;
                for (int j = 0; j < entryCount; j++)
                {
                    if (entries[j].hashCode >= 0 && @default.Equals(entries[j].value, value))
                    {
                        return true;
                    }
                }
            }
            return false;
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            int i = FindEntry(key);
            if (i >= 0)
            {
                value = entries[i].value;//赋值
                return true;
            }
            value = default(TValue);//没有这个值，也要赋值，因为out
            return false;
        }

        public int Count
        {
            get { return entryCount - freeCount; }
        }

        // 实现迭代功能的核心部分
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        // 枚举器实现
        public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
        {
            private readonly MyDictionary<TKey, TValue> dictionary;
            private int index;
            private KeyValuePair<TKey, TValue> current;
            private readonly int version;

            public Enumerator(MyDictionary<TKey, TValue> dictionary)//构造函数
            {
                this.dictionary = dictionary;
                index = -1;
                current = default;
                version = dictionary.version;//快照，保证迭代过程中没有版本变化
            }

            public KeyValuePair<TKey, TValue> Current => current;

            object IEnumerator.Current => current;

            public void Dispose()
            { }

            public bool MoveNext()
            {
                if (version != dictionary.version)
                    throw new InvalidOperationException("字典在枚举过程中被修改");

                while (++index < dictionary.entryCount)
                {
                    // 仅处理有效条目（hashCode >= 0）
                    if (dictionary.entries[index].hashCode >= 0)
                    {
                        current = new KeyValuePair<TKey, TValue>(
                            dictionary.entries[index].key,
                            dictionary.entries[index].value
                        );
                        return true;
                    }
                }

                index = dictionary.entryCount;
                current = default;
                return false;
            }

            public void Reset()
            {
                index = -1;
                current = default;
            }
        }
    }
}